|
In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time〔; .〕 and has several applications in dynamic graph algorithms and graph drawing. The basic structures underlying the SPQR tree, the triconnected components of a graph, and the connection between this decomposition and the planar embeddings of a planar graph, were first investigated by ; these structures were used in efficient algorithms by several other researchers〔E.g., and , both of which are cited as precedents by Di Battista and Tamassia.〕 prior to their formalization as the SPQR tree by . ==Structure== An SPQR tree takes the form of an unrooted tree in which for each node ''x'' there is associated an undirected graph or multigraph ''G''''x''. The node, and the graph associated with it, may have one of four types, given the initials SPQR: *In an S node, the associated graph is a cycle graph with three or more vertices and edges. This case is analogous to series composition in series-parallel graphs; the S stands for "series".〔.〕 *In a P node, the associated graph is a dipole graph, a multigraph with two vertices and three or more edges, the planar dual to a cycle graph. This case is analogous to parallel composition in series-parallel graphs; the P stands for "parallel".〔 *In a Q node, the associated graph has a single real edge. This trivial case is necessary to handle the graph that has only one edge. In some works on SPQR trees, this type of node does not appear in the SPQR trees of graphs with more than one edge; in other works, all non-virtual edges are required to be represented by Q nodes with one real and one virtual edge, and the edges in the other node types must all be virtual. *In an R node, the associated graph is a 3-connected graph that is not a cycle or dipole. The R stands for "rigid": in the application of SPQR trees in planar graph embedding, the associated graph of an R node has a unique planar embedding.〔 Each edge ''xy'' between two nodes of the SPQR tree is associated with two directed ''virtual edges'', one of which is an edge in ''Gx'' and the other of which is an edge in ''Gy''. Each edge in a graph ''Gx'' may be a virtual edge for at most one SPQR tree edge. An SPQR tree ''T'' represents a 2-connected graph ''GT'', formed as follows. Whenever SPQR tree edge ''xy'' associates the virtual edge ''ab'' of ''Gx'' with the virtual edge ''cd'' of ''Gy'', form a single larger graph by merging ''a'' and ''c'' into a single supervertex, merging ''b'' and ''d'' into another single supervertex, and deleting the two virtual edges. That is, the larger graph is the 2-clique-sum of ''Gx'' and ''Gy''. Performing this gluing step on each edge of the SPQR tree produces the graph ''GT''; the order of performing the gluing steps does not affect the result. Each vertex in one of the graphs ''Gx'' may be associated in this way with a unique vertex in ''GT'', the supervertex into which it was merged. Typically, it is not allowed within an SPQR tree for two S nodes to be adjacent, nor for two P nodes to be adjacent, because if such an adjacency occurred the two nodes could be merged into a single larger node. With this assumption, the SPQR tree is uniquely determined from its graph. When a graph ''G'' is represented by an SPQR tree with no adjacent P nodes and no adjacent S nodes, then the graphs ''G''''x'' associated with the nodes of the SPQR tree are known as the triconnected components of ''G''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「SPQR tree」の詳細全文を読む スポンサード リンク
|